package priv.conceit.study.leetcode.medium;


import java.util.Objects;

/**
 * 编号622
 * 设计循环队列
 * <a href="https://leetcode-cn.com/problems/design-circular-queue/"></a>
 * 设计你的循环队列实现
 * 循环队列是一种线性数据结构，
 * 其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”
 * <p>
 * 循环队列的一个好处是我们可以利用这个队列之前用过的空间。
 * 在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间
 * 但是使用循环队列，我们能使用这些空间去存储新的值。
 * 你的实现应该支持如下操作
 * <p>
 * MyCircularQueue(k): 构造器，设置队列长度为 k
 * Front: 从队首获取元素。如果队列为空，返回 -1
 * Rear: 获取队尾元素。如果队列为空，返回 -1
 * enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真
 * deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真
 * isEmpty(): 检查循环队列是否为空
 * isFull(): 检查循环队列是否已满
 * <p>
 * 说明:
 * 所有的值都在 0 至 1000 的范围内。
 * 操作数将在 1 至 1000 的范围内。
 * 请不要使用内置的队列库
 *
 * @author conceit
 * @since 1.0.0, 2019/8/23
 */
public class DesignCircularQueue {

	/**
	 * ["MyCircularQueue","enQueue","Rear","Rear","deQueue","enQueue","Rear","deQueue","Front","deQueue","deQueue","deQueue"]
	 * [[6],[6],[],[],[],[5],[],[],[],[],[],[]]
	 *
	 * 预期
	 * [null,true,6,6,true,true,5,true,-1,false,false,false]
	 * @param args
	 */
	public static void main(String[] args) {
		DesignCircularQueue designCircularQueue=new DesignCircularQueue(6);
		System.out.println(designCircularQueue.enQueue(6));
		System.out.println(designCircularQueue.Rear());
		System.out.println(designCircularQueue.Rear());
		System.out.println(designCircularQueue.deQueue());
		System.out.println(designCircularQueue.enQueue(5));
		System.out.println(designCircularQueue.Rear());
		System.out.println(designCircularQueue.deQueue());
		System.out.println(designCircularQueue.Front());
		System.out.println(designCircularQueue.deQueue());
		System.out.println(designCircularQueue.deQueue());
		System.out.println(designCircularQueue.deQueue());

	}


	/**
	 * 初始化数组
	 */
	private int [] array;
	/**
	 * 目前的元素总数
	 */
	private int count;
	private int headIndex;
	private int tailIndex;

	/**
	 * Initialize your data structure here. Set the size of the queue to be k.
	 */
	public DesignCircularQueue(int  k) {

		array = new int [k];
		count = 0;
		headIndex = -1;
		tailIndex = -1;
	}

	/**
	 * 先进先出
	 * 判断当前数组是否已满
	 * <p>
	 * 已满则return false
	 * <p>
	 * 为空则
	 * 在在arr[0]处插入元素
	 * 并将队头队尾指针指向arr[0]处
	 * <p>
	 * 没满则
	 * 判断队尾 位置是否==length
	 * 没超过则
	 * 向队尾+1 位置 插入元素
	 * 并将队尾指针指向队尾+1处
	 * <p>
	 * 等于则
	 * 向arr[0]处 插入元素
	 * 并将队尾指针指向arr[0]处
	 *
	 * @param value
	 * @return
	 */
	public boolean enQueue(Integer value) {

		if (isFull()) {
			return Boolean.FALSE;
		}
		if(Objects.isNull(value)){
			return Boolean.FALSE;
		}
		if (count == 0) {
			headIndex = 0;
			array[0] = value;
			tailIndex++;
		} else {
			//当前队尾是否已经超过length
			if(tailIndex+1==array.length){
				tailIndex = 0;
				array[0] = value;
			}
			//否则直接向后加
			else{
				tailIndex++;
				array[tailIndex] = value;
			}
		}
		count++;
		return Boolean.TRUE;
	}

	/**
	 * 删除,从队首删除
	 *
	 * 如果count为0
	 * 直接返回
	 *
	 * 如果count为1，或herd==tail
	 * 出队
	 * herd和tail指向-1
	 *
	 * 其他情况则
	 * 出队
	 * herd++；
	 *
	 * @return
	 */
	public boolean deQueue() {
		if (count == 0) {
			return Boolean.FALSE;
		}
		if(count==1){
			headIndex=-1;
			tailIndex=-1;
		}else{
			headIndex++;
		}
		count--;
		return Boolean.TRUE;
	}


	public int Rear() {
		return tailIndex==-1?-1:array[tailIndex];

	}

	/**
	 * 从队首获取元素。如果队列为空，返回 -1 。
	 * @return
	 */
	public int Front() {
		return headIndex==-1?-1:array[headIndex];
	}


	public boolean isEmpty() {
		return count == 0;
	}

	public boolean isFull() {
		return count == array.length;
	}
}
